Programming

Question

Programming

Manu · Accepted Answer

Step 1:

"Stack.py"

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def size(self):
        return len(self.items)

"lab04.py"

from Stack import Stack

def solveMaze(maze, startX, startY):
    stack = Stack()
    stack.push((startX, startY))
    rows, cols = len(maze), len(maze[0])
    path = []  # To store the path

    # Directions for movement (right, down, left, up)
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    while not stack.isEmpty():
        x, y = stack.pop()

        if maze[x][y] == 'G':  # Goal found
            path.append((x, y))
            print(f"Path to goal exists: {path}")
            return True

        if maze[x][y] == '+':  # Wall or already visited
            continue

        # Mark the current cell as visited
        maze[x][y] = '+'
        path.append((x, y))

        # Push neighboring cells to the stack
        for dx, dy in directions:
            newX, newY = x + dx, y + dy
            if 0 <= newX < rows and 0 <= newY < cols and maze[newX][newY] != '+':
                stack.push((newX, newY))

    print("No path to goal")
    return False

# Test the solveMaze function
if __name__ == "__main__":
    maze = [
        [' ', ' ', ' ', '+', ' '],
        ['+', '+', ' ', '+', ' '],
        [' ', ' ', ' ', ' ', ' '],
        [' ', '+', '+', '+', ' '],
        [' ', ' ', ' ', 'G', ' ']
    ]

    startX, startY = 0, 0  # Starting position
    result = solveMaze(maze, startX, startY)
    if not result:
        print("No path to goal")

Explanation

Neighbor Check Logic: The check condition if 0 <= newX < rows and 0 <= newY < cols and maze[newX][newY] != '+': ensures that we only push valid cells onto the stack that are within bounds and not already visited or walls.
Printing Path: If the goal is found, it prints the path. If no path is found, it prints "No path to goal."

Stack Class Implementation (Stack.py):

__init__: Initializes an empty list to store stack items.
isEmpty: Checks if the stack is empty.
push: Adds an item to the top of the stack.
pop: Removes and returns the item from the top of the stack.
peek: Returns the item at the top of the stack without removing it.
size: Returns the number of items in the stack.

Maze Solving Function (solveMaze in lab04.py):

Initializes a stack and pushes the starting position onto it.
Uses a loop to process each position by popping it from the stack.
Checks if the current position is the goal (G).
Marks the current position as visited by setting it to +.
Pushes neighboring positions (right, down, left, up) onto the stack if they are within bounds and not visited.

Step 2 Output of above code:

$ python lab04.py
Path to goal exists: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3)]

Computer science

Computer science

Manu

Answer

Extracted Transcript from Images